package org.example.hansp.recursion;

import java.util.ArrayList;
import java.util.List;

import static org.example.hansp.recursion.MiGong.barrier;
import static org.example.hansp.recursion.MiGong.printMap;

public class MiGong02 {
    // 定义四个方向的移动
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private static int minPathLength=Integer.MAX_VALUE;// 存储最短路径长度
    private static List<int[]> shortestPath = new ArrayList<>();// 存储最短路径

    public static int findShortestPath(int[][] map,int row,int col,int pathLength,List<int[]> currentPath) {
        // 如果到达终点，更新最短路径长度和路径
        if(row==map.length-2&&col==map[0].length-2){
            if (pathLength < minPathLength) {
                minPathLength = pathLength;
                shortestPath = new ArrayList<>(currentPath);
            }
            return minPathLength;
        }
        // 标记当前格子为已访问
        map[row][col]=2;
        currentPath.add(new int[]{row, col});
        // 尝试四个方向移动
        for(int[] direction:DIRECTIONS) {
            int newRow=row+direction[0];
            int newCol=col+direction[1];
// 检查新位置是否在迷宫内且可走
            if (newRow >= 1 && newRow < map.length-1 && newCol >= 1 && newCol < map[0].length-1 && map[newRow][newCol] == 0) {
                findShortestPath(map, newRow, newCol, pathLength + 1,currentPath);
            }
        }
        // 回溯：将当前格子标记为未访问，并移除当前路径
        map[row][col] = 0;
        currentPath.remove(currentPath.size() - 1);

        return minPathLength == Integer.MAX_VALUE ? -1 : minPathLength;
    }
    public static void main(String[] args) {
        int[][] map = new int[8][7];
        MiGong.originMap(map);

        barrier(map);
        printMap(map);
        System.out.println("============================");
        List<int[]> initialPath = new ArrayList<>();
        int result = findShortestPath(map, 1, 1, 0, initialPath);

        if (result != -1) {
            System.out.println("The shortest path length is: " + result);
            System.out.println("The shortest path is: ");
            for (int[] step : shortestPath) {
                System.out.println("(" + step[0] + ", " + step[1] + ")");
            }
        } else {
            System.out.println("No path found.");
        }

    }
}
